Multi-stage Clos arrays are used regularly in the networking industry to switch information from input to output in a switching system. A block diagram of a typical three stage Clos array is shown in FIG. 1A, comprising a plurality (K) of ingress devices 102, a plurality (P) of center stage devices 104, and a plurality (K) of egress devices 106. In a Clos array, each device (i.e. ingress, center stage, and egress) is capable of connecting any of its inputs to any of its outputs without restriction. In this example the plurality of ingress devices 102 and the plurality of egress devices 106 are equal in number. However, this equal number of egress and ingress devices is not needed.
To qualify as a Clos array, a three stage switching array has to meet at least two main requirements. A first requirement is that each ingress device 102 must have at least one logical link to each center stage device 104, and each egress device 106 must have at least one logical link to each center stage device 104. By logical link, it is meant that an information path exists between two devices so that the two devices can send/receive communications to/from each other. This requirement of the Clos array ensures that information from any ingress device 102 can be switched to any egress device 106 through any center stage device 104. Hereinafter, the term “logical link” will be used to refer to a logical link as defined above, and the term “link” will be used to refer to a physical link (or line), such as an electrical or optical fiber line. Note that a physical link need not be equivalent to a logical link. For example, a physical link may comprise a plurality of logical links and a plurality of physical links may comprise a logical link.
A second requirement of a Clos array is that the logical links need to be symmetrical. That is, the amount of bandwidth on each logical link needs to be the same. If these requirements are satisfied, then a three stage switching array can qualify as a Clos array.
In the array of FIG. 1A, each ingress device 102 has a link to each center stage device 104. Likewise, each egress device 106 has a link to each center stage device 104. Because there are a K number of ingress devices 102 and a K number of egress devices 106, and because each device 102, 106 has a link to each center stage device 104, it means that each center stage device 104 has a K number of input ports for receiving the links from the ingress devices 102, and a K number of output ports for coupling to the egress devices 106. Thus, each center stage device 104 is said to have a K number of input/output ports.
As shown in FIG. 1A, each link between a center stage device 104 and an ingress 102 or egress 106 device carries an N number of time slots or bandwidth units (BU's) (a BU may be viewed as a unit of information that is carried on a link). Since each center stage device 104 has K input/output ports, and each port handles N BU's, the total amount of BU's handled by each center stage device 104 is K*N.
When it comes to implementing switching arrays that support a large number of inputs and outputs, the configuration of FIG. 1A is limited. This limitation is due to the fact that the total capacity of the switching array can only be increased by either using larger ingress and egress devices 102 and 106 or using a larger number of ingress and egress devices and hence a larger center stage device 104.
To elaborate, suppose that it is desired to implement a switching array comprising 72 ingress devices 102 and 72 egress devices 106, with each link carrying 18 BU's. To implement this switching array with the configuration of FIG. 1A, each center stage device 104 would have to have 72 input/output ports, and would need to be able to handle 1,296 BU's. Likewise, to implement a switching array with 144 ingress and egress devices, with each link carrying 18 BU's, each center stage device 104 would need to have 144 input/output ports, and would need to be able to handle 2,592 BUs. Due to practical cost and technological constraints, it may not be possible to implement large center stage devices 104. Even if it were, it would be clear that the size of the array would be limited by the capabilities of the center stage devices 104. At any given time with regard to such technology, a center stage device 104 will be able to have only so many input/output ports and process only so much overall BUs. As an alternative, one could simply increase the size of the ingress and egress devices but this simply moves the problem away from the center stage device to the ingress and egress devices. In either case the size of the array that can be achieved using the configuration of FIG. 1A will be limited by the current state of technology. Thus, as this discussion shows, the configuration of FIG. 1A has limits to scalability.
As an alternative to a three stage array, a five or more stage switching array may be implemented. A sample five-stage array 150 is shown in FIG. 1B, comprising a plurality (K) of ingress devices 102 and egress devices 106, a plurality (P) of center stage devices 104, and a plurality (L) of 2nd stage devices 120 and 4th stage devices 130. By increasing the number of switching stages, it is possible to grow the overall array without proportionately growing the number of input/output ports of each device 102, 104, 106 or the amount of BU's handled by each device 102, 104, 106. Thus, adding more switching stages makes the array more scalable.
There are significant drawbacks to this approach, however. For one thing, implementing additional switching stages significantly increases the number of switching devices that need to be implemented in the array, which in turn, significantly increases the cost of the overall array. Also, implementing more switching stages significantly increases the complexity and cost involved in controlling the switching in the overall array. As part of the switch array control, a control algorithm is run to determine what configuration of the switch array will realize the desired connection of array inputs to array outputs. This configuration needs to be loaded to each of the switch devices in the array. Increasing the number of switching stages adds complexity to both the control algorithm and to the method of distributing the configuration information to all the switching devices. For example, in array 150 of FIG. 1B each device is dynamically reconfigured to realize a given set of connections through the array. Because the 2nd and 4th stage device 120, 130 are dynamically reconfigurable, a switching algorithm needs to take the switching capabilities of these devices into account in determining how to switch information through the array 150. Factoring these devices 120, 130 into the switching determination significantly increases the complexity of the determination. This increases the amount of time needed to compute a switching scheme for the array, which in turn degrades the array's ability to make fast switching changes. In addition, this complicates methods for implementing a switching scheme for multi-cast functionality. Because of these and other drawbacks, the approach of adding more switching stages to expand a switching array is less desirable.
As the above discussion shows, the current approaches to implementing switching arrays do not enable the arrays to be efficiently expanded. As a result, an improved approach is needed.